package structure;

import java.util.Arrays;
import java.util.Random;

public class MyPriorityQueue {
    private static void random(int[] arr) {
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            //[0,10)
            arr[i] = random.nextInt(100);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[11];
        random(arr);
        MyPriorityQueue queue1 = new MyPriorityQueue();
        queue1.offer(90);
        queue1.offer(80);
        queue1.offer(70);
        queue1.offer(3);
        queue1.offer(6);
        queue1.offer(9);
        System.out.println("原数组: " + Arrays.toString(queue1.queue));

        int size = queue1.size;
        while (size != 0) {
            System.out.println(queue1.poll());
            size--;
        }
        System.out.println("排序后: " + Arrays.toString(queue1.queue));
    }

    private static final int DEFAULT_CAPACITY = 11;
    private int[] queue;

    private int size;

    public MyPriorityQueue() {
        this.queue = new int[DEFAULT_CAPACITY];
    }

    public void initQueue(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            queue[i] = arr[i];
            size++;
        }
    }

    public void createHeap() {
        for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) {
            downward(parent);
        }
    }

    private void downward(int parent) {
        int child = 2 * parent + 1;
        while (child < size) {
            if (child + 1 < size && queue[child] > queue[child + 1]) {
                child = child + 1;
            }

            if (queue[child] < queue[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    private void swap(int child, int parent) {
        int tmp = queue[child];
        queue[child] = queue[parent];
        queue[parent] = tmp;
    }

    // 堆的插入
    public void offer(int val) {
        int i = size;
        if (i == 0) {
            queue[0] = val;
        }else {
            upward(val, i);
        }
        size++;
    }

    private void upward(int val, int child) {
        while (child != 0) {
            int parent = (child - 1) / 2;
            if (val < queue[parent]) {
                queue[child] = queue[parent];
                child = parent;
            }else {
                break;
            }
        }
        queue[child] = val;
    }

    private int poll() {
        int result = queue[0];
        swap(0, size - 1);
        size--;
        downward(0);
        return result;
    }
}
